package nowCoder;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by Ghost on 2015/1/27 0027.
 * 有如下图所示(左)的一棵二叉树， 请设计一种遍历方式，使得按照如下方式（右）输出各个元素：
 * （从下到上， 从右到左输出， 要求每层之间换行， 同行元素之间用tab分割，写出完整代码）。
 */

public class PrintTree {
    class TreeNode{
        TreeNode left,right;
        String tag;
        TreeNode(String tag){
            this.tag = tag;
        }
    }


    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    Stack<TreeNode> stack = new Stack<TreeNode>();

    public void print(TreeNode root){
        if(root==null)
            return;
        LinkedList<Integer> printEachTime = new LinkedList<Integer>();
        queue.add(root);
        int count;
        while(!queue.isEmpty()){
            count = queue.size();
            printEachTime.addFirst(count);
            while(count>0){
                TreeNode t = queue.poll();
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }
                stack.push(t);
                count--;
            }
        }

        while(!stack.isEmpty()){
            for(Integer i:printEachTime){
                for(int ii=0;ii<i-1;ii++){
                    TreeNode tt = stack.pop();
                    System.out.print(tt.tag+"   ");
                }
                System.out.println(stack.pop().tag);
            }
        }
    }

    public static void main(String[] args){
        PrintTree printTree = new PrintTree();
        PrintTree.TreeNode root = printTree.new TreeNode("1");
        root.left = printTree.new TreeNode("2");
        root.right = printTree.new TreeNode("3");
        root.left.left = printTree.new TreeNode("4");
        root.left.right = printTree.new TreeNode("5");
        root.left.left.left = printTree.new TreeNode("6");

        printTree.print(root);
    }
}
